Book embedding

In graph theory, book embedding is a generalization of planar embedding to nonplanar surfaces in the form of a book, a collection of pages (half-planes) joined together at the spine of the book (the shared boundary of all the half-planes). The vertices of the graph are embedded on the spine, and each edge must lie in one of the pages. Book embeddings and book thickness were first studied by L. Taylor Ollman in 1973,[1] and have since been studied by many other researchers from the points of view of graph theory, VLSI,[2] and graph drawing.

Contents

Definitions

A book B is a topological space consisting of a single line ℓ called the spine of B and a collection of k half-planes, with k ≥ 1, called the pages of B, each having ℓ as its boundary.

A book drawing of a graph G onto a book B is a drawing of G on B such that:

A book embedding of G onto B is a graph embedding of G into B, i.e., the drawing of G on B without crossings. The book thickness or pagenumber of G is the minimum number of pages required for a book embedding of G.

Relations to other graph properties

The book thickness of a graph is at most 1 if and only if it is outerplanar. The book thickness is at most two if and only if the graph is a subgraph of a planar graph with a Hamiltonian cycle;[3] for instance, the Goldner–Harary graph, a non-Hamiltonian maximal planar graph, provides an example of a planar graph that does not have book thickness two.[3] Since finding Hamiltonian cycles in maximal planar graphs is NP-complete, so is the problem of testing whether the book thickness is two. All planar graphs have book thickness at most four, and some planar graphs have book thickness exactly four.[4] Graphs of treewidth k have book thickness at most k + 1.[5] Graphs of genus g have book thickness O(√g).[6]

Generalizations

A generalization of this concept is to allow the embedded edges to cross the spine. Some authors call this notion topological book embedding of graphs, and it is a topic of algorithmic research as well. [7]

References

  1. ^ Ollmann, L. Taylor (1973), "On the book thicknesses of various graphs", in Hoffman, Frederick; Levow, Roy B.; Thomas, Robert S. D., Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, VIII, p. 459 .
  2. ^ Chung, Fan R. K.; Leighton, Frank Thompson; Rosenberg, Arnold L. (1987), "Embedding graphs in books: A layout problem with applications to VLSI design", SIAM. Journal on Algebraic and Discrete Methods 8 (1): 33–58, doi:10.1137/0608002, http://www.math.ucsd.edu/~fan/mypaps/fanpap/fc82embedding.pdf .
  3. ^ a b Bernhart, Frank R.; Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B 27 (3): 320–331, doi:10.1016/0095-8956(79)90021-2 .
  4. ^ Yannakakis, Mihalis (1986), "Four pages are necessary and sufficient for planar graphs", Proc. 18th ACM Symp. Theory of Computing (STOC), pp. 104–108, doi:10.1145/12130.12141, ISBN 0897911938 .
  5. ^ Dujmović, Vida; Wood, David R. (2007), "Graph treewidth and geometric thickness parameters", Discrete & Computational Geometry 37 (4): 641–670, doi:10.1007/s00454-007-1318-7 .
  6. ^ Malitz, S. M (1988), "Genus g graphs have pagenumber O(√g)", Proceedings of the 29th Annual Symposium on Foundations of Computer Science 00: 458–468, doi:10.1109/SFCS.1988.21962, ISBN 0-8186-0877-3 .
  7. ^ Miyaguchi, Miki (2006), "Topological book embedding of bipartite graphs", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E89-A (5): 1223–1226, doi:10.1093/ietfec/e89-a.5.1223 .